

# 统计小于n的数中有几个质数
# 质数：如果x不能整除[2, x**0.5]之间的任意一个数则该数为质数

# 解法一：漏了11*11=121这些
# class Solution:
#     def countPrimes(self, n: int) -> int:
#         # 错误思路：只要不是2，3，5，7的倍数，一定为质数
#         count = 0
#         while n > 1:
#             if (n % 2 != 0 and n % 3 != 0 and n % 5 != 0 and n % 7 != 0) or (n == 2 or n == 3 or n == 5 or n == 7):
#                 count += 1
#                 print(n)
#             n -= 1
#
#         return count

# 解法二:厄拉多塞筛法
# 西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，
# 减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。
# 具体操作：先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；
# 第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；
# 现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，
# 一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0

        res = [1] * n
        res[0] = res[1] = 0
        for i in range(2, int(n**0.5)+1):
            if res[i]:
                res[i*i:n:i] = [0] * len(res[i*i:n:i])

        return sum(res)


if __name__ == "__main__":
    s = Solution()
    res = s.countPrimes(10)
    print(res)
